其实只有 道题。两道不是网络流,另一道是假题。
一.最大流问题
简单题
1.P2756 飞行员配对方案问题
经典的二分图最大匹配。
建立源点与汇点,分别向二分图的其中一部分连容量为 的边。
可匹配的点之间也连一条边,容量随意。
最后跑最大流即可。
方案可以根据残余网络构造出来。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 100 , MAXM = MAXN * ( MAXN + 2 );
struct Edge {
int v , flw , nxt;
Edge(){}
Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
Graph[ ++ Enum ] = Edge( u , 0 , Head[ v ] ); Head[ v ] = Enum;
}
int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
memcpy( cur , Head , sizeof( Head ) );
memset( lev , -1 , sizeof( lev ) );
queue< int > Que;
lev[ S ] = 0 , Que.push( S );
while( !Que.empty() ) {
int u = Que.front(); Que.pop();
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw ;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int d = dfs( v , t , min( f , flw ) );
if( d > 0 ) {
Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
return d;
}
}
}
return 0;
}
int Dinic( int S , int T ) {
int Mxf = 0;
while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
return Mxf;
}
int n , m , S , T;
int main( ) {
scanf("%d %d",&m,&n); S = n + 1 , T = S + 1;
for( int u , v ; scanf("%d %d",&u,&v) && u != -1 && v != -1 ; )
Add_Edge( u , v , 1 );
for( int i = 1 ; i <= m ; i ++ ) Add_Edge( S , i , 1 );
for( int i = m + 1 ; i <= n ; i ++ ) Add_Edge( i , T , 1 );
printf("%d\n", Dinic( S , T ) );
for( int i = 1 ; i <= m ; i ++ ) {
for( int j = Head[ i ] ; j ; j = Graph[ j ].nxt ) {
int v = Graph[ j ].v , flw = Graph[ j ].flw;
if( ( m + 1 <= v && v <= n ) && !flw ) { printf("%d %d\n", i , v ); break; }
}
}
return 0;
}
2.P3254 圆桌问题
首先建立 个点,表示每个单位,并从原点向他们连容量为 的边。
然后再建立 个点,表示每个餐桌,因为同一公司只能坐一人所以每个公司向每个餐桌连容量为 的边。
最后看最大流是否为满流即可。方案可根据残余网络构造。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 420 , MAXM = 3 * MAXN * MAXN;
struct Edge {
int v , flw , nxt;
Edge(){}
Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
Graph[ ++ Enum ] = Edge( u , 0 , Head[ v ] ); Head[ v ] = Enum;
}
int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
memcpy( cur , Head , sizeof( Head ) );
memset( lev , -1 , sizeof( lev ) );
queue< int > Que;
lev[ S ] = 0 , Que.push( S );
while( !Que.empty() ) {
int u = Que.front(); Que.pop();
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw ;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int d = dfs( v , t , min( f , flw ) );
if( d > 0 ) {
Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
return d;
}
}
}
return 0;
}
int Dinic( int S , int T ) {
int Mxf = 0;
while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
return Mxf;
}
int n , m , Sumr , S , T;
vector< int > p;
int main( ) {
scanf("%d %d",&m,&n); S = m + n + 1 , T = S + 1;
for( int i = 1 , r ; i <= m ; i ++ ) {
scanf("%d",&r); Sumr += r;
Add_Edge( S , i , r );
}
for( int i = 1 , c ; i <= n ; i ++ ) {
scanf("%d",&c);
Add_Edge( m + i , T , c );
}
for( int i = 1 ; i <= m ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
Add_Edge( i , m + j , 1 );
int Ans = Dinic( S , T );
if( Ans != Sumr ) return printf("0") & 0;
printf("1\n");
for( int i = 1 ; i <= n ; i ++ ) {
p.clear();
for( int j = Head[ i ] ; j ; j = Graph[ j ].nxt ) {
int v = Graph[ j ].v , flw = Graph[ j ].flw;
if( ( m + 1 <= v && v <= m + n ) && !flw ) p.push_back( v - m );
}
sort( p.begin() , p.end() );
for( int j = 0 ; j < p.size() ; j ++ ) printf("%d ", p[ j ] );
printf("\n");
}
return 0;
}
3.P2763 试题库问题
与题 2 类似。
首先建立 个点,表示每道题,每道题只能选一次所以从源点连容量为 的边。
然后再建立 个点,表示试题类型,每种类型向汇点连容量为需要选出试题个数的边。
最后看最大流是否为满流即可。方案可根据残余网络构造。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 1020 , MAXM = MAXN * ( MAXN + 2 );
struct Edge {
int v , flw , nxt;
Edge(){}
Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
Graph[ ++ Enum ] = Edge( u , 0 , Head[ v ] ); Head[ v ] = Enum;
}
int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
memcpy( cur , Head , sizeof( Head ) );
memset( lev , -1 , sizeof( lev ) );
queue< int > Que;
lev[ S ] = 0 , Que.push( S );
while( !Que.empty() ) {
int u = Que.front(); Que.pop();
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw ;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int d = dfs( v , t , min( f , flw ) );
if( d > 0 ) {
Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
return d;
}
}
}
return 0;
}
int Dinic( int S , int T ) {
int Mxf = 0;
while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
return Mxf;
}
int n , m , k , S , T;
vector< int > id[ 25 ];
int main( ) {
scanf("%d %d",&k,&n);
S = n + k + 1 , T = S + 1;
for( int i = 1 , r ; i <= k ; i ++ ) {
scanf("%d",&r); m += r;
Add_Edge( n + i , T , r );
}
for( int i = 1 ; i <= n ; i ++ ) Add_Edge( S , i , 1 );
for( int i = 1 , p ; i <= n ; i ++ ) {
scanf("%d",&p);
for( int j = 1 , ty ; j <= p ; j ++ ) {
scanf("%d", &ty );
Add_Edge( i , n + ty , 1 );
}
}
int Ans = Dinic( S , T );
if( Ans != m ) return puts( "No Solution!" ) & 0;
for( int i = 1 ; i <= n ; i ++ ) {
for( int j = Head[ i ] ; j ; j = Graph[ j ].nxt ) {
int v = Graph[ j ].v , flw = Graph[ j ].flw;
if( ( n + 1 <= v && v <= n + k ) && !flw ) id[ v - n ].push_back( i );
}
}
for( int i = 1 ; i <= k ; i ++ ) {
printf("%d:", i );
for( int j = 0 ; j < id[ i ].size() ; j ++ ) printf(" %d", id[ i ][ j ] );
printf("\n");
}
return 0;
}
中等题
4.P2764 最小路径覆盖问题
首先每个点用一条边覆盖,为了使路径尽可能少,我们要连接一些路径。
将每个点拆成两个点 ,对于 这条边,连接 并将容量设为 ,如果这条边有流则表示将 的路径合并。
然后连接 ,容量也设为 (要求顶点不相交,每个点只能连接一次)
最后图的最大流便是连接的最大数量,答案为 。
方案直接记录后继节点就可以了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 300 , MAXM = 7000;
struct node {
int v , flow , nxt;
}Graph[ 2 * MAXM + 5 ];
int tot = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
Graph[ ++ tot ] = { v , f , Head[ u ] };
Head[ u ] = tot;
}
int n , m , s , t;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
memset( lev , -1 , sizeof( lev ) );
memcpy( cur , Head , sizeof( Head ) );
queue< int > Que;
Que.push( s ) , lev[ s ] = 0;
while( !Que.empty( ) ) {
int u = Que.front( ); Que.pop( );
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flow;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flow;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int mf = dfs( v , t , min( f , flw ) );
if( mf ) {
Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
if( u != s && v > n ) sta[ v - n ] = 1;
nxt[ u ] = v;
return mf;
}
}
}
return 0;
}
int Dinic( int s , int t ) {
int Maxf = 0;
while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
for( int i = 1 ; i <= n ; i ++ )
if( !sta[ i ] ) {
printf("%d", i );
int u = i;
while( nxt[ u ] && nxt[ u ] != t ) {
printf(" %d", nxt[ u ] - n );
u = nxt[ u ] - n;
}
printf("\n");
}
return Maxf;
}
int main( ) {
scanf("%d %d",&n,&m);
s = 2 * n + 1 , t = 2 * n + 2;
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
Add_Edge( u , v + n , 1 );
Add_Edge( v + n , u , 0 );
}
for( int i = 1 ; i <= n ; i ++ )
Add_Edge( s , i , 1 ) , Add_Edge( i , s , 0 );
for( int i = 1 ; i <= n ; i ++ )
Add_Edge( i + n , t , 1 ) , Add_Edge( t , i + n , 0 );
printf("%d\n", n - Dinic( s , t ) );
return 0;
}
5.P2774 方格取数问题
选出的格子不能相邻,这是此题的关键。
如果两个格子相邻,那么它们坐标和的奇偶性一定不同。
将限制条件看成一条边,那么图是一个二分图。分别从源点和汇点向两部分连边,容量即为格子里的数。
不选格子里的数相当删去于将源点/汇点与该点的边。
求出图的最小割即可。
因为不能改变限制条件,所以二分图内部的容量设为极大值。
注意不要重复建边。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 10000 , MAXM = 6 * MAXN;
struct Edge {
int v , flw , nxt;
Edge(){}
Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
Graph[ ++ Enum ] = Edge( u , 0 , Head[ v ] ); Head[ v ] = Enum;
}
int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
memcpy( cur , Head , sizeof( Head ) );
memset( lev , -1 , sizeof( lev ) );
queue< int > Que;
lev[ S ] = 0 , Que.push( S );
while( !Que.empty() ) {
int u = Que.front(); Que.pop();
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw ;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int d = dfs( v , t , min( f , flw ) );
if( d > 0 ) {
Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
return d;
}
}
}
return 0;
}
int Dinic( int S , int T ) {
int Mxf = 0;
while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
return Mxf;
}
int n , m , a[ 105 ][ 105 ] , Suma , S , T;
int hs( int x , int y ) { return ( x - 1 ) * 100 + y; }
int main( ) {
scanf("%d %d",&n,&m); S = hs( n + 1 , 1 ) , T = hs( n + 1 , 2 );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
scanf("%d",&a[ i ][ j ]) , Suma += a[ i ][ j ];
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
if( ( i + j ) & 1 ) Add_Edge( S , hs( i , j ) , a[ i ][ j ] );
else Add_Edge( hs( i , j ) , T , a[ i ][ j ] );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
if( ( i + j ) & 1 ) {
if( i != 1 ) Add_Edge( hs( i , j ) , hs( i - 1 , j ) , Inf );
if( i != n ) Add_Edge( hs( i , j ) , hs( i + 1 , j ) , Inf );
if( j != 1 ) Add_Edge( hs( i , j ) , hs( i , j - 1 ) , Inf );
if( j != m ) Add_Edge( hs( i , j ) , hs( i , j + 1 ) , Inf );
}
printf("%d\n", Suma - Dinic( S , T ) );
return 0;
}
6.P2766 最长不下降子序列问题
首先可以 dp 求得以 结尾的最长不下降子序列。
第一问的答案 。
然后源点向所有 的点连容量为 的边,汇点向所有 的点连容量为 的边。
那么 dp 转移可以这样刻画:
对于 的 ,在它们之间连一条容量为 的边。
这样不能保证每个点只被选 次,所以将每个点拆成两个点即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 1000 , MAXM = MAXN * ( MAXN + 2 );
struct Edge {
int v , flw , nxt;
Edge(){}
Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
Graph[ ++ Enum ] = Edge( u , 0 , Head[ v ] ); Head[ v ] = Enum;
}
int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
memcpy( cur , Head , sizeof( Head ) );
memset( lev , -1 , sizeof( lev ) );
queue< int > Que;
lev[ S ] = 0 , Que.push( S );
while( !Que.empty() ) {
int u = Que.front(); Que.pop();
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw ;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int d = dfs( v , t , min( f , flw ) );
if( d > 0 ) {
Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
return d;
}
}
}
return 0;
}
int Dinic( int S , int T ) {
int Mxf = 0;
while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
return Mxf;
}
int n , a[ MAXN + 5 ] , S , T;
int s , dp[ MAXN + 5 ];
int main( ) {
scanf("%d",&n); S = 2 * n + 1 , T = S + 1;
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
if( n == 1 ) return printf("%d\n%d\n%d\n",1,1,1) & 0;
for( int i = 1 ; i <= n ; i ++ ) {
dp[ i ] = 1;
for( int j = 1 ; j < i ; j ++ )
if( a[ j ] <= a[ i ] ) dp[ i ] = max( dp[ i ] , dp[ j ] + 1 );
s = max( s , dp[ i ] );
}
printf("%d\n", s );
for( int i = 1 ; i <= n ; i ++ ) {
if( dp[ i ] == 1 ) Add_Edge( S , i , 1 );
if( dp[ i ] == s ) Add_Edge( n + i , T , 1 );
}
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j < i ; j ++ )
if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , 1 );
printf("%d\n", Dinic( S , T ) );
memset( Head , 0 , sizeof( Head ) ); Enum = 1;
for( int i = 1 ; i <= n ; i ++ ) {
if( dp[ i ] == 1 ) Add_Edge( S , i , i == 1 ? Inf : 1 );
if( dp[ i ] == s ) Add_Edge( n + i , T , i == n ? Inf : 1 );
}
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j < i ; j ++ )
if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , ( i == 1 || i == n ) ? Inf : 1 );
printf("%d\n", Dinic( S , T ) );
return 0;
}
进阶题
7.P2765 魔术球问题
考虑将两个能放在一起的球之间连一条边,因为要求球要依次放,所以边由编号较小的球连向编号较大的。
那么一个柱子可看作有向图上的一条简单路径。
原问题即转化为 条不相交的简单路径最多能覆盖多少点。
很像第 题,枚举答案可以发现前几项:
作差得到:
那么可以先算出球数,然后用第四题的方法构造答案即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f
const int MAXN = 3200 , MAXM = MAXN * ( MAXN + 2 );
struct node { int v , flw , nxt; }Graph[ 2 * MAXM + 5 ];
int Enum = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
Graph[ ++ Enum ] = { v , f , Head[ u ] }; Head[ u ] = Enum;
Graph[ ++ Enum ] = { u , 0 , Head[ v ] }; Head[ v ] = Enum;
}
int n , k , S , T;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
memset( lev , -1 , sizeof( lev ) );
memcpy( cur , Head , sizeof( Head ) );
queue< int > Que;
Que.push( s ) , lev[ s ] = 0;
while( !Que.empty( ) ) {
int u = Que.front( ); Que.pop( );
for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
if( flw > 0 && lev[ v ] == -1 )
lev[ v ] = lev[ u ] + 1 , Que.push( v );
}
}
return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
if( u == t ) return f;
for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
int v = Graph[ i ].v , flw = Graph[ i ].flw;
cur[ u ] = i;
if( flw > 0 && lev[ u ] < lev[ v ] ) {
int mf = dfs( v , t , min( f , flw ) );
if( mf ) {
Graph[ i ].flw -= mf; Graph[ i ^ 1 ].flw += mf;
if( u != S && v > n ) sta[ v - n ] = 1;
nxt[ u ] = v;
return mf;
}
}
}
return 0;
}
int Dinic( int s , int t ) {
int Maxf = 0;
while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
for( int i = 1 ; i <= n ; i ++ )
if( !sta[ i ] ) {
printf("%d", i );
int u = i;
for( int u = i ; nxt[ u ] && nxt[ u ] != t ; u = nxt[ u ] - n ) printf(" %d", nxt[ u ] - n );
printf("\n");
}
return Maxf;
}
bool sqt[ MAXN * MAXN + 5 ];
int main( ) {
scanf("%d",&k); n = ( k * ( k + 2 ) + ( k & 1 ) - 2 ) / 2;
printf("%d\n", n );
S = 2 * n + 1 , T = S + 1;
for( int i = 1 ; i <= n ; i ++ ) sqt[ i * i ] = 1;
for( int i = 1 ; i <= n ; i ++ )
for( int j = i + 1 ; j <= n ; j ++ )
if( sqt[ i + j ] ) Add_Edge( i , n + j , 1 );
for( int i = 1 ; i <= n ; i ++ ) Add_Edge( S , i , 1 );
for( int i = 1 ; i <= n ; i ++ ) Add_Edge( n + i , T , 1 );
Dinic( S , T );
return 0;
}